package com.origin.niuke.tree;

import general_class.TreeNode;

/**
 * 二叉树的直径
 * 算法：二叉树
 * 计算每个节点的左右子树的最大深度, 然后加起来, 取最大
 * 在计算深度的时候, 就已经知道节点的左右子树的最大深度, 直接比较即可
 *
 * @author yezh
 * @date 2023/2/10 22:13
 */
public class NC195 {

    int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        // write code here
        dfs(root);
        return ans;
    }

    int dfs(TreeNode node) {
        if (node == null) return 0;
        int left = dfs(node.left);
        int right = dfs(node.right);
        ans = Math.max(ans, left + right);
        return Math.max(left, right) + 1;
    }

}
